//滑动窗口的最大值
//https://leetcode.cn/problems/sliding-window-maximum/description/?envType=study-plan-v2&envId=top-100-liked

#include <string>
#include <iostream>
#include <map>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
    public:
    vector<int> maxInWindows(const vector<int> & num, unsigned int size) {

        std::vector<int >maxInWindows;
        if (num.size() >= size && size >= 1) {

            std::deque<int> index;   // 存放索引号,存放第一个最大值。
            for (unsigned int i = 0; i < size; ++i) {
                while (!index.empty() && num[i] >= num[index.back()]) {
                    index.pop_back();
                }
                index.push_back(i);
            }
            maxInWindows.push_back(num[index.front()]);

            for (unsigned int i = size; i < num.size(); ++i) {

                // 如果值是大于deque里面的最大值的，那么直接删掉。
                while (!index.empty() && num[i] >= num[index.back()]) {
                    index.pop_back();
                }
                //如果是小，那么就先留着，这样队列的头部始终拿着最大值。
                if (!index.empty() && index.front() <= (int)(i - size)) {
                    index.pop_front();
                }
                index.push_back(i);
                maxInWindows.push_back(num[index.front()]);
            }

        }
        return maxInWindows;
    }
};